#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=322 lang=cpp
 *
 * [322] 零钱兑换
 */

// @lc code=start
class Solution {
public:
    // int coinChange(vector<int>& coins, int amount) {
    //     // dp[i][j] 前i中凑成j的最小硬币数目
    //     // dp[i - 1][j], dp[i - 1][j - vi] + 1
    //     int len = coins.size();
    //     vector<vector<int>> dp(len + 1, vector<int>(amount + 1, amount + 1));
    //     dp[0][0] = 0;
    //     for (int i = 1; i <= len; i++) {
    //         for (int j = 0; j <= amount; j++) {
    //             dp[i][j] = dp[i - 1][j];
    //             if (j - coins[i - 1] >= 0) dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
    //         }
    //     }
    //     return dp[len][amount] <= amount ? dp[len][amount] : -1;
    // }

    int coinChange(vector<int>& coins, int amount) {
        vector<int> F(amount + 1, amount + 1);
        F[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i - coins[j] >= 0) F[i] = min(F[i], F[i - coins[j]] + 1);
            }
        }
        return F[amount] <= amount ? F[amount] : -1;
    }
};
// @lc code=end

